//给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现
//在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。 
//
// 
//
// 示例 1: 
//
// 
//输入: temperatures = [73,74,75,71,69,72,76,73]
//输出: [1,1,4,2,1,1,0,0]
// 
//
// 示例 2: 
//
// 
//输入: temperatures = [30,40,50,60]
//输出: [1,1,1,0]
// 
//
// 示例 3: 
//
// 
//输入: temperatures = [30,60,90]
//输出: [1,1,0] 
//
// 
//
// 提示： 
//
// 
// 1 <= temperatures.length <= 10⁵ 
// 30 <= temperatures[i] <= 100 
// 
//
// Related Topics 栈 数组 单调栈 👍 1603 👎 0


package LeetCode.editor.cn;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author ldltd
 * @date 2023-09-11 11:37:33
 * @description 739.每日温度
 */
public class DailyTemperatures{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 Solution solution = new DailyTemperatures().new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
		 /*单调栈，还没找到的时候加入栈，当出现一个大于顶部的温度时
		 * 依次检查，通过i-保存得到下标得到天数更新答案*/
    public int[] dailyTemperatures(int[] temperatures) {
		int[] res = new int[temperatures.length];
		Deque<Integer>stack=new LinkedList<Integer>();
		//stack存温度的下标
		for (int i=0;i<temperatures.length;i++) {
			//如果栈不会空，且当天的温度大于栈中的温度，则保存答案
			while (!stack.isEmpty()&&temperatures[stack.peek()]<temperatures[i]){
				int preIndex=stack.pop();
				res[preIndex]=i-preIndex;
			}
			//最后把当前温度入栈
				stack.push(i);
		}
		return res;
	}
}
//leetcode submit region end(Prohibit modification and deletion)

}
